package com.peng.leetcode.array;

import java.util.Deque;
import java.util.LinkedList;

/**
 * RemoveKdigits
 * <p>
 * <p>
 * 402. 移掉K位数字
 * <p>
 * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 *
 * @author: lupeng6
 * @create: 2021/3/30 14:24
 */
public class RemoveKdigits {

    public static void main(String[] args) {
        String num = "1432219";
        int k = 3;
        System.out.println(new RemoveKdigits().removeKdigits(num, k));
    }

    /**
     * 双端队列，
     * 当钱的数字小于前面的数字， 移除前面的。
     * 单调栈
     *
     * @author lupeng6
     * @date 2021/3/30 14:35
     */
    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<>();
        int len = num.length();
        for (int i = 0; i < len; i++) {
            char c = num.charAt(i);
            while (!deque.isEmpty() && deque.peekLast() > c && k > 0) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(c);
        }

        for (int i = 0; i < k; i++) {
            deque.pollLast();
        }

        // 合并数字 str
        StringBuilder builder = new StringBuilder();
        boolean loadingZero = true;
        while (!deque.isEmpty()) {
            Character ch = deque.pollFirst();
            if (loadingZero && ch == '0') {
                continue;
            }
            loadingZero = false;
            builder.append(ch);
        }
        String string = builder.toString();
        if (string.length() == 0) {
            return "0";
        }
        return string;
    }


}
